package sort.test57;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/19 9:23
 */
public class Solution1 {

    // 自己的写法，时间较高
    public int[][] insert(int[][] intervals, int[] newInterval) {
        Stack<int[]> satck = new Stack<>();
        int len = intervals.length;
        int[][] newArr = new int[len + 1][2];
        int i = 0;
        newArr[i++] = newInterval;
        for (int j = 0; j < len; j++) {
            newArr[i++] = intervals[j];
        }
        return merge(newArr);
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return intervals;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        Stack<int[]> stack = new Stack<>();
        for (int[] t : intervals) {
            if (stack.isEmpty() || stack.peek()[1] < t[0]) {
                stack.push(t);
            } else {
                int[] p = stack.pop();
                p[1] = Math.max(t[1], p[1]);
                stack.push(p);
            }
        }
        int[][] res = new int[stack.size()][2];
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}
